//在给定的 m x n 网格
// grid 中，每个单元格可以有以下三个值之一： 
//
// 
// 值 0 代表空单元格； 
// 值 1 代表新鲜橘子； 
// 值 2 代表腐烂的橘子。 
// 
//
// 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 
//
// 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
//输出：-1
//解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
// 
//
// 示例 3： 
//
// 
//输入：grid = [[0,2]]
//输出：0
//解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 10 
// grid[i][j] 仅为 0、1 或 2 
// 
//
// Related Topics 广度优先搜索 数组 矩阵 👍 791 👎 0


package com.tyrone.leetcode.editor.cn;

public class RottingOranges {
    public static void main(String[] args) {
        Solution solution = new RottingOranges().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 如果每次遍历都直接把当前分钟的要变坏的橙子全部找到，那么每次遍历就是每分钟，相当于问要遍历多少此
         * 二维数组其实可以优化掉，对于要变化成坏的橘子的地方，直接加上k（第k分钟变化）来判断是否是本轮次的就可以了
         * @param grid
         * @return
         */
        public int orangesRotting(int[][] grid) {

            for (int k = 0;; k++) {
                int newNum = 0;
                for (int i = 0; i < grid.length; i++) {
                    for (int j = 0; j < grid[0].length; j++) {
                        if (grid[i][j] == 2 + k) {
                            if (i > 0) {
                                grid[i - 1][j] = grid[i - 1][j] == 1 ? 2+k+1 : grid[i - 1][j];
                            }
                            if (i < grid.length - 1) {
                                grid[i + 1][j] = grid[i + 1][j] == 1 ? 2+k+1  : grid[i + 1][j];
                            }
                            if (j > 0) {
                                grid[i][j - 1] = grid[i][j - 1] == 1 ? 2+k+1  : grid[i][j - 1];

                            }
                            if (j < grid[0].length - 1) {
                                grid[i][j + 1] = grid[i][j + 1] == 1 ? 2+k+1  : grid[i][j + 1];
                            }
                            newNum++;
                        }
                    }
                }
                if (newNum==0){
                    int allZero = 0;
                    for (int i = 0; i < grid.length; i++) {
                        for (int j = 0; j < grid[0].length; j++) {
                            if (grid[i][j] == 1)
                                return -1;
                            if (grid[i][j] != 0)
                                allZero = 1;
                        }
                    }
                    if (allZero==0) return 0;
                    return k - 1;
                }
            }
        }
//        public int orangesRotting(int[][] grid) {
//            int[][] arr = new int[grid.length][grid[0].length];
//            for (int i = 0; i < grid.length; i++) {
//                for (int j = 0; j < grid[0].length; j++) {
//                    if (grid[i][j] == 2) {
//                        arr[i][j] = 1;
//                    }
//                }
//            }
//            for (int k = 1;; k++) {
//                int newNum = 0;
//                for (int i = 0; i < grid.length; i++) {
//                    for (int j = 0; j < grid[0].length; j++) {
//                        if (grid[i][j] == 2 && arr[i][j] == k) {
//                            if (i > 0) {
//                                grid[i - 1][j] = grid[i - 1][j] == 1 ? 2 : grid[i - 1][j];
//                                arr[i - 1][j] = arr[i - 1][j] < k + 1 &&arr[i - 1][j]!=0 ? arr[i - 1][j] : k + 1;
//                            }
//                            if (i < grid.length - 1) {
//                                grid[i + 1][j] = grid[i + 1][j] == 1 ? 2 : grid[i + 1][j];
//                                arr[i + 1][j] = arr[i + 1][j] < k + 1 &&arr[i + 1][j]!=0 ? arr[i + 1][j] : k + 1;
//                            }
//                            if (j > 0) {
//                                grid[i][j - 1] = grid[i][j - 1] == 1 ? 2 : grid[i][j - 1];
//                                arr[i][j - 1] = arr[i][j - 1] < k + 1 &&arr[i][j - 1]!=0 ? arr[i][j - 1] : k + 1;
//
//                            }
//                            if (j < grid[0].length - 1) {
//                                grid[i][j + 1] = grid[i][j + 1] == 1 ? 2 : grid[i][j + 1];
//                                arr[i][j + 1] = arr[i][j + 1] < k + 1 &&arr[i][j + 1]!=0 ? arr[i][j + 1] : k + 1;
//                            }
//                            newNum++;
//                        }
//                    }
//                }
//                if (newNum==0){
//                    int allZero = 0;
//                    for (int i = 0; i < grid.length; i++) {
//                        for (int j = 0; j < grid[0].length; j++) {
//                            if (grid[i][j] == 1)
//                                return -1;
//                            if (grid[i][j] != 0)
//                                allZero = 1;
//                        }
//                    }
//                    if (allZero==0) return 0;
//                    return k - 2;
//                }
//            }
//        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}